#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[405],sum=0,t1,t2,ans=-1e18,dp[405][405],b[405][405],qian[405],hou[405];
set<int> e[405];
bool v[405];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void dfs(int k,int g){
	if(((n+1-k)*(n+1-k)*sum+g)<=ans) return;
	if(k==(n+1)){
		ans=max(ans,g);
		return;
	}
	for(int j=1;j<=n;j++){
		if(v[j]) continue;
		for(set<int>::iterator i=e[j].begin();i!=e[j].end();i++){
			int o=*i;
			a[o]+=a[j];
			e[o].erase(j);
		}
		v[j]=1;
		dfs(k+1,g+a[j]);
		v[j]=0;
		for(set<int>::iterator i=e[j].begin();i!=e[j].end();i++){
			int o=*i;
			a[o]-=a[j];
			e[o].insert(j);
		}
	}
}
inline int js(int x){
	return hou[x]*x+qian[x-1]+a[1]*(x-1);
}
inline void solve1(){
	sort(a+2,a+1+n);
	for(int i=2;i<=n;i++) qian[i]=qian[i-1]+a[i];
	for(int i=n;i>=2;i--) hou[i]=hou[i+1]+a[i];
	for(int i=2;i<=(n+1);i++) ans=max(ans,js(i));
	cout<<ans;
}
signed main(){
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		sum+=a[i];
	}
	for(int i=1;i<n;i++){
		t1=read(),t2=read();
		e[t1].insert(t2);
		e[t2].insert(t1);
	}
	if(n<=10){
		dfs(1,0);
		cout<<ans;
	}
	else solve1();
	return 0;
}

